/**
 * 青蛙跳台阶,假设青蛙每次都可以跳1台阶或2个台阶,台阶总共有n个,计算青蛙总共有多少种跳台阶组合,跳1阶和跳2阶是有顺序之分的。
 * 先人工分析下前几种台阶的跳法组合
 * 1阶时，只有1种跳法
 * 2阶时，有2种跳法
 * 3阶时，有3种跳法
 * 4阶时，第一跳可以是跳1阶或跳2阶，跳1阶时，以第一阶为起点，后面剩3阶，后面就是3阶的跳法了；第一跳是2阶是，后面剩2阶，就和2阶高度的跳法一样了，总结就是相当于2阶和3阶高度的和，有5种跳法
 * 5阶时，第一跳可以是1阶，可以是2阶，剩下就和4阶高度的跳法+3阶高度的跳法一致了。总结下来就是，每个阶高度的跳法，可以分解成低一阶和低两阶的效果，其实就是前两种跳法之和。
 * 这种方式也叫斐波那契数列，每一个数字都是它前两个数字之和。
 */
public class FrogJump {
    public static void main(String[] args) {
        int n = 20;
        int[] arr = new int[n];  //定义一个整形数组，用来存放每种台阶高度时的跳台阶方法数，数组作者后面会讲。
        arr[0]=1; //数组下标是从0开始的，arr[0]表示1阶，所有只有1种跳法；因为我们知道了规律，后面每种台阶高度都需要前2种台阶高度计算，所以先给前两种台阶高度的跳法定义好。
        arr[1]=2;  //arr[1]表示2阶，所有2种跳法；
        for (int i = 2; i < n; i++) {  //这里i不是从0开始的，因为我们知道了前两阶的跳法数字，后面的数字需要以前两阶数字来计算。且数组是从0开始的，所以这里i从第三个开始即i=2，10个台阶就是0-9,i<10
            arr[i] = arr[i-1]+arr[i-2];
            System.out.println("第"+(i+1)+"个台阶的跳法有"+arr[i]+"种");  //i+1是因为数组从0开始的，第i阶表示的实际上是人类认知的第i+1阶。不用()括起来，和字符串相加就变成字符串了，而不是它的值。
        }
    }
}
